package com.xzx.algorithms.sparsearray;

import java.util.HashMap;
import java.util.Map;

/**
 * 稀疏数组解决的是大量数据是重复的二维数组的场景
 *
 * @author xinzhixuan
 * @version 1.0
 * @date 2024/11/17 17:28
 */
public class Test {
    public static void main(String[] args) {
        int[][] sparseArray = new int[9][9];
        sparseArray[3][3] = 1;
        sparseArray[5][6] = 2;
        sparseArray[6][8] = 2;

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(sparseArray[i][j] + "\t");
            }
            System.out.println();
        }



        System.out.println("===========稀疏数组转压缩数组==================");
        int[][] compressArray = toCompressArray(sparseArray, 0);

        for (int i = 0; i < compressArray.length; i++) {
            for (int j = 0; j < compressArray[0].length; j ++) {
                System.out.print(compressArray[i][j] + "\t");
            }
            System.out.println();
        }


        System.out.println("===========压缩数组还原稀疏数组==================");
        int[][] newSparseArray = new  int[compressArray[0][0]][compressArray[0][1]];
        int row = compressArray[0][0];
        int col = compressArray[0][1];
        int defaultValue = compressArray[0][2];
        int compressArrayColIndex = 1;// 从第二行开始判断赋值
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (compressArrayColIndex < compressArray.length
                        && i == compressArray[compressArrayColIndex][0]
                        && j == compressArray[compressArrayColIndex][1]) {
                    newSparseArray[i][j] = compressArray[compressArrayColIndex][2];
                    compressArrayColIndex++;
                } else {
                    newSparseArray[i][j] = defaultValue;
                }
                System.out.print( newSparseArray[i][j] + "\t");
            }
            System.out.println();
        }

    }
    public static int[][] toCompressArray(int[][] sparseArray, int defaultValue) {
        int rows = 0;
        // 判断默认值是多少
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int[] a : sparseArray) {
            for (int i : a) {
                if (i != defaultValue) {
                    rows ++;
                }
            }
        }

        int[][] compressArray = new int[rows + 1][3];
        compressArray[0][0] = sparseArray.length;
        compressArray[0][1] = sparseArray[0].length;
        compressArray[0][2] = defaultValue;// 存放默认值


        int rowIndex = 1;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (sparseArray[i][j] != 0) {
                    compressArray[rowIndex][0] = i;
                    compressArray[rowIndex][1] = j;
                    compressArray[rowIndex][2] = sparseArray[i][j];
                    rowIndex++;
                }
            }
        }
        return  compressArray;
    }
}
